# O(nk^2)
# class Solution(object):
#     def minCostII(self, costs):
#         """
#         :type costs: List[List[int]]
#         :rtype: int
#         """
#         n = len(costs)
#         k = len(costs[0])
#         p = [[0 for _ in range(k)] for _ in range(n)]
#         for j in range(k):
#             p[0][j] = costs[0][j]
#         for i in range(1, n):
#             for j in range(k):
#                 min_value = 2001
#                 for m in range(k):
#                     if j != m:
#                         min_value = min(p[i - 1][m] + costs[i][j], min_value)
#                 p[i][j] = min_value
#         return min(p[-1])

# O(nk)
class Solution(object):
    def minCostII(self, costs):
        """
        :type costs: List[List[int]]
        :rtype: int
        """
        n = len(costs)
        k = len(costs[0])
        p = [[0 for _ in range(k)] for _ in range(n)]
        for j in range(k):
            p[0][j] = costs[0][j]
        for i in range(1, n):
            if p[i - 1][0] <= p[i - 1][1]:
                min_value = [[0, p[i - 1][0]], [1, p[i - 1][1]]]
            else:
                min_value = [[1, p[i - 1][1]], [0, p[i - 1][0]]]
            for j in range(2, k):
                if p[i - 1][j] < min_value[0][1]:
                    min_value[1][0] = min_value[0][0]
                    min_value[1][1] = min_value[0][1]
                    min_value[0][0] = j
                    min_value[0][1] = p[i - 1][j]
                else:
                    if p[i - 1][j] < min_value[1][1]:
                        min_value[1][0] = j
                        min_value[1][1] = p[i - 1][j]
            print(min_value)
            for j in range(k):
                if j != min_value[0][0]:
                    p[i][j] = min_value[0][1] + costs[i][j]
                else:
                    p[i][j] = min_value[1][1] + costs[i][j]
        print(p)
        return min(p[-1])


data = Solution()
costs = [[19, 3, 18, 4, 13, 1, 12, 6, 3, 12, 3, 3, 9], [11, 5, 9, 16, 2, 19, 15, 10, 13, 20, 15, 2, 13],
         [19, 6, 18, 7, 6, 10, 11, 13, 8, 19, 4, 14, 18], [3, 18, 18, 9, 3, 6, 18, 11, 7, 4, 13, 3, 12]]
print(data.minCostII(costs))
